from typing import List


class Solution:
    def __init__(self):
        self.path = []
        self.result = 0

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ret = []

        def tra(start):
            if self.result == n and k == len(self.path):
                ret.append(self.path[:])
                return
            for i in range(start, 10):
                # 剪枝，超过长度为k的就跳过
                if len(self.path) >= k or self.result > n:
                    return
                self.path.append(i)
                self.result += i
                # print(self.path)
                tra(i + 1)
                self.path.pop()
                self.result -= i

        tra(1)
        return ret
# print(Solution().combinationSum3(3,7))
